package dp;

import java.util.Scanner;

public class MostAttack {



    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int heroN = in.nextInt();
        int z = in.nextInt();
        int[][] arrs = new int[heroN][z];
        int res = 0;
        for (int a=0;a<heroN;a++){
            for (int b =0;b<z;b++){
                arrs[a][b] = in.nextInt();
            }
        }
        System.out.println(getMaxAttackWithDP(arrs,heroN,z));
    }

    /*
     2 3
     5 6 7
     7 8 18
    * 输入n   m   n代表有n个战士   m代表有m件装备
    * 输入n个长度为m的数组  分别代表n号战士装备x （1<x<=m）可以获得的攻击力  求所有战士可以获得的最大攻击力
    *
    * */
    //暴力递归
    public static int getMaxAttack(int[][] arrs,int hn,int less){
        if (less<=0 || hn == arrs.length){
            return 0;
        }
        int max = 0;
        for (int a=0;a<=less;a++){
            int temp = (a==0?0:arrs[hn][a-1]) + getMaxAttack(arrs,hn+1,less-a);
            max= Math.max(temp,max);
        }
        return max;
    }
    //动态规划

    public static int getMaxAttackWithDP(int[][] arrs,int hn,int less){
        //dp表示第n+1号英雄及后续英雄有less件装备可以选择的时候时  自身及后续英雄可以获得的最大的攻击力
        int[][] dp = new int[hn][less+1];   //hn表示英雄  less表示剩余装备数
        for(int a=0;a<=less;a++){
            dp[hn-1][a] = a==0?0:arrs[hn-1][a-1];
        }

        for (int x=hn-2;x>=0;x--){
            for (int y = 0;y<=less;y++){
                if (y==0){
                    dp[x][y] = 0;
                }else{
                    int max = dp[x][0];
                    for (int a=0;a<=y;a++){
                        int num = a==0?0:arrs[x][a-1];
                        max = Math.max(dp[x+1][y-a]+num,max);
                    }
                    dp[x][y] = max;
                }
            }
        }
        int res = 0;
        for (int a:dp[0]){
            res = Math.max(a,res);
        }
        return res;
    }
    /*
4 3
19 2 3
21 2 3
11 2 3
2 80 3

2 3
5 6 7
7 8 9
    * */
}
